import { swap } from 'helper/sortTest'

/**
 * NOTE: 插入排序, 从后面找到小的元素插入到前面已经排好序的位置
 * @param arr
 */
export function insertSort(arr: number[]) {
  for (let i = 1; i < arr.length; i++) {
    // 向前遍历, 插入到对应的位置
    for (let j = i; j > 0; j--) {
      // 如果小于上一个元素, 就交换位置, 否则就不需要交换, 那么就退出循环,
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j - 1)
      } else {
        // 对比选择排序, 插入排序可以提前结束内循环
        break
      }
    }
  }
}

// 优化, 减少交换的次数, 将当前元素复制出来, 然后将前面需要交换的元素向后移动, 然后就赋值
// 如果一个序列基本上是有序的, 那么插入排序就很快
export function insertSortEnhance(arr: number[]) {
  for (let i = 1; i < arr.length; i++) {
    let item = arr[i]
    // 向前遍历, 插入到对应的位置
    let j
    for (j = i; j > 0 && arr[j - 1] > item; j--) { // 如果当前元素小于上一个元素, 那么将上一个元素向后移动
      // 向后移动
      arr[j] = arr[j - 1]
    }
    arr[j] = item
  }
}

export function insertSort2(arr: number[], l: number, r: number) {
  for (let i = l; i <= r; i++) {
    let item = arr[i]
    // 向前遍历, 插入到对应的位置
    let j
    for (j = i; j > 0 && arr[j - 1] > item; j--) { // 如果当前元素小于上一个元素, 那么将上一个元素向后移动
      // 向后移动
      arr[j] = arr[j - 1]
    }
    arr[j] = item
  }
}
